package leetcode.code0301;

import java.util.ArrayList;
import java.util.List;

public class Solution1 extends Solution301 {

	List<String> ans;
	int len;
	char[] chars;

	@Override
	public List<String> removeInvalidParentheses(String s) {
		ans = new ArrayList<>();
		chars = s.toCharArray();
		len = chars.length;
		int[] remove = this.removeNum(chars);
		this.removeIndex(0, remove[0], remove[1]);
		return ans;
	}

	private void removeIndex(int index, int left, int right) {
		if (index == len) {
			String str = check(chars);
			if (str != null) {
				if (ans.indexOf(str) == -1) {
					ans.add(str);
				}
			}
			return;
		}
		this.removeIndex(index + 1, left, right);
		char c = chars[index];
		if (c == '(' && left > 0) {
			chars[index] = ' ';
			this.removeIndex(index + 1, left - 1, right);
			chars[index] = c;
		} else if (c == ')' && right > 0) {
			chars[index] = ' ';
			this.removeIndex(index + 1, left, right - 1);
			chars[index] = c;
		}
	}

	private String check(char[] chars) {
		StringBuffer sb = new StringBuffer();
		int left = 0;
		for (char c : chars) {
			if (c == ' ')
				continue;
			sb.append(c);
			if ((c != '(' && c != ')'))
				continue;
			if (c == ')') {
				if (left != 0) {
					left--;
				} else {
					return null;
				}
			} else {
				left++;
			}
		}
		if (left == 0) {
			return sb.toString();
		} else {
			return null;
		}
	}

	private int[] removeNum(char[] chars) {
		int left = 0;
		int right = 0;
		for (char c : chars) {
			if ((c == ' ') || (c != '(' && c != ')'))
				continue;
			if (c == ')') {
				if (left != 0) {
					left--;
				} else {
					right++;
				}
			} else {
				left++;
			}
		}
		return new int[] { left, right };
	}

	public static void main(String[] args) {
		Solution1 so = new Solution1();
		so.debug1();
		so.debug2();
//		so.debug3();
//		so.debug4();
	}

}
